The present invention relates to a processor to execute processing a desired operation according to a program prepared therefor, and in particular, to an array-type processor including a plurality of processor elements arranged in a two-dimensional array shape.
The known programmable devices include various types of microprocessors in which instructions or commands stored in a memory are read in an order therefrom and are sequentially executed.
That is, in such a microprocessor, instructions each of which executes quite simple processing are ordered in a combination and are executed in an order to execute a target sequence of processing.
However, only several instructions can be simultaneously executed by one microprocessor. This limits improvement of processing performance or capacity.
Specifically, when the same processing is to be executed for a large amount of data, it is necessary to repeatedly execute sequential processing. Therefore, processing performance cannot be improved.
To surmount the limitation, a technique to concurrently (simultaneously) execute instructions by a plurality of processor elements is already known. Concretely, there exist various techniques depending on electric connections between the processor elements.
In the xe2x80x9cIntroduction To The Configurable, Highly Parallel Computerxe2x80x9d (IEEE Computer, January 1982), Lawrence Snyder proposed one of the techniques. According to the proposal, a plurality of processor elements are disposed in an array shape and are electrically connected to each other using programmable switches (to be referred to as a first prior art technique hereinbelow).
The microprocessor of the first prior art technique executes concurrent processing by a plurality of processors to improve processing performance when compared with processing executed by one processor. Since processor elements are electrically connected by programmable switches, the electric connections between the elements can be established according to a purpose. Particularly, efficient processing can be executed in applications of data processing fields.
In the microprocessor, different kinds of processing, that is, processing based on an operating unit such as a data path and processing of a random logic circuit such as a control circuit are executed only by an array section of each processor element. It is therefore necessary to add general processing capacity to each processor element.
To meet requirements for miniaturization and high performance of microprocessors, a technique to customize the function of each processor element for it processing purpose is to be developed. However, the technique is quite difficult and hence there arises a problem that the requirements for miniaturization and high performance of microprocessors cannot be satisfied.
It is therefore an object of the present invention to provide an array-type processor, devised to remove the problem of the prior art, including processor elements arranged in an array shape and electrically connected by programmable switches. The array-type processor includes a data path section to primarily conduct processing of operation and a state transition control section configured for easy implementation of a state transition function or unit to control state transition. Each section is customized for each processing purpose to thereby miniaturize its size and to improve processing performance.
To achieve the object above in accordance with the present invention, there is provided an array-type processor comprising a state transition control section including a state transition table memory for storing a state transition table in which transition rules between a plurality of operation states are written, and a sequencer section for controlling, using the state transition table memory, transitions between the operation states and for determining the operation states at a particular point of time; and a data path section independent of said state transition control section, including a plurality of processor elements for executing processing of operations according to the operation states determined by said state transition control section and a plurality of programmable switch elements for connecting the processor elements to each other according to the operation states determined by said state transition control section. The processor elements and said programmable switch elements are electrically connected in a two-dimensional array shape. Each said processor element includes an instruction code memory for storing a plurality of instruction codes, an instruction decoder for decoding an instruction code read from said instruction code memory, and an operating section for executing processing of operation according to the instruction code decoded by said instruction decoder. Each said programmable switch element includes a connection layout information memory for storing a plurality of sets of connection layout information, the information indicating a connection layout between said processor elements and said programmable switch elements and/or between said programmable switch elements.
As above, the data path section to primarily conduct operation and the state transition control section are separated from each other and each there of is configured in a customized manner according to its processing purpose. Therefore, the operation and the control operation can be efficiently implemented and the processing can be effectively executed. This minimizes the array-type processor in size, and processing performance is improved.
Additionally, in accordance with the present invention, in the array-type processor, the state transition control section conducts a control operation according to a transition of the operation state by said state transition control section itself and/or a transition of the operation state by inputting an event from said data path section and/or a transition of the operation state by inputting an event from an external device.
The configuration allows the array-type processor to carry out a flexible control operation for detailed items and hence processing performance is improved.
Moreover, in accordance with the present invention, the array-type processor further comprises an operation control bus for electrically connecting said state transition control section to said data path section. The state transition control section outputs an address of said instruction code memory and/or an address of said connection layout information memory via said operation control bus according to the operation states at a particular point of time.
Thanks to the structure, the array-type processor can efficiently delivers control signals from the state transition control unit to the processor elements and the programmable switch elements.
Furthermore, in accordance with the present invention, the array-type processor further comprises one or more said operation control buses. The state transition control section outputs the address to said operation control buses. Each of the processor elements and/or each of the programmable switch elements select/selects one of said operation control buses to input the address.
In consequence, the array-type processor can effectively operate the processor elements and hence processing performance is increased.
In addition, in accordance with the present invention, in the array-type processor, the state transition control section concurrently supplies independent said addresses respectively to said processor elements and respectively to said programmable switch elements.
In this constitution, the array-type processor can effectively operate the processor elements in the data path section, which improves processing performance.
Furthermore, in accordance with the present invention, in the array-type processor, the processor elements and/or the programmable switch elements are classified into groups. The address is supplied to one of the groups.
Consequently, the array-type processor can effectively operate the processor elements classified into groups in the data path section and hence processing performance is increased.
Moreover, in accordance with the present invention, in the array-type processor, the address is supplied only to a part of the processor elements and/or a part of the programmable switch elements according to the operation states at a particular point of time. Each of other said processor elements and other said programmable switch elements continuously uses said address immediately used before the operation state at a particular point of time.
In this structure, the array-type processor can continuously execute processing by the processor elements and can accomplish a flexible control operation for detailed items, which leads to improvement of processing performance.
Additionally, in accordance with the present invention, in the array-type processor, the operation control buses are arranged for said processor elements and said programmable switch elements. The state transition control section outputs said address to said operation control buses. Each of said processor elements and/or said programmable switch elements selects one of said operation control buses in the vicinity thereof to obtain said address.
This simplifies the constitution of the array-type processor and hence the control operation is advantageously simplified.
Furthermore, in accordance with the present invention, in the array-type processor, the operation control buses are disposed respectively or independently for said processor elements and said programmable switch elements. The independent operation control buses are independent of each other. The operation control buses conduct mutually independent control operations for said processor elements and said programmable switch elements, respectively.
In consequence, the array-type processor is simplified in constitution and the control operation is facilitated.
In addition, in accordance with the present invention, in the array-type processor, each processor element includes a register for recording operation data.
Therefore, wiring efficiency between the operating section and the register is improved in the array-type processor. This minimizes the size of the array-type processor and increases processing performance.
Furthermore, in accordance with the present invention, in the array-type processor, each processor element executes processing of operation for external input data received from an external device or for the operation data under control of said state transition control section and outputs a result of the processing as output data to the external device or records a result of the processing in said register.
Thanks to the structure, the array-type processor can efficiently execute processing of operation and hence processing efficiency is improved.
Additionally, in accordance with the present invention, the array-type processor further includes an event notifying bus for electrically connecting said state transition control section to said data path section. The data path section notifies a result of processing as an event via said event notifying bus to said state transition control section.
Consequently, the array-type processor can achieve a flexible control operation for detailed items and can execute processing with high processing efficiency.
Furthermore, in accordance with the present invention, in the array-type processor, the sequencer section controls state transitions from the operation states to the same operation states or other different operation states according to the state transition rules written in said state transition table memory and sets said same operation states or said other different operation states as new operation states.
In the construction, the array-type processor can effectively conduct a control operation and hence processing efficiency is improved.
Additionally, in accordance with the present invention, in the array-type processor, the state transition table is recorded in a list format including a plurality of script entries of a plurality of operation states. Each of the script entries includes a state number to identify a first state at a point of time, a state number to identify a second state of a state transition destination at a subsequent point of time, and a state transition condition for a transition from the first state to the second state.
In the structure of the array-type processor, since the state transition table is configured in a list form including a plurality of script entries of operation states, the control operation can be efficiently and easily carried out with higher processing efficiency.
Furthermore, in accordance with the present invention, the state transition control section further comprises a control information memory for controlling an address of said instruction code memory and/or an address of said connection layout information memory in association with the first state number at the point of time or the second state number at the subsequent point of time. The address of said instruction code memory and/or the address of said connection layout information memory are/is identified using said control information memory according to the first state number at the point of time or the second state number at the subsequent point of time identified using said state transition table.
As above, the identification of the first state number at the point of time or the second state number at the subsequent point of time as the state transition destination and the identification of the address of said instruction code memory and/or the address of said connection layout information memory are/is accomplished using respectively different memories. Therefore, the circuit area on which memories are mounted can be reduced and the bit width of the connection control bus can be minimized without decreasing the degree of freedom to determine the state transition destination.
Additionally, in accordance with the present invention, the array-type processor further comprises a control information memory for controlling the next state number of the subsequent point of time and an address of said instruction code memory and/or an address of said connection layout information memory in association with the first state number at the point of time. The state transition table identifies the next state number of the subsequent point of time and the address of said instruction code memory and/or the address of said connection layout information memory using the first state number at the point of time.
Not only the next state number of the subsequent point of time, but also the address of said instruction code memory at the point of time can be identified according to the first state number of the point of time. This minimizes the number of operations to refer to memories and hence the processing can be executed at a higher speed.
Furthermore, in accordance with the present invention, in the array-type processor, the state transition table includes an event state transition table containing the entries, each said entry including a state number at a point of time, a state number at a subsequent point of time, and a state transition condition and a default state transition table containing the entries, each said entry includes a state number at a point of time and a state number of a subsequent point of time. A state transition is achieved when the state transition condition is satisfied, according to said event state transition table. A state transition is achieved when the state transition condition is not satisfied, according to said default state transition table.
Thanks to the configuration, the array-type processor can effectively achieve the state transition and the control operation is facilitated.
Moreover, in accordance with the present invention, in the array-type processor, a plurality of said script entries correspond to said state number at a certain point of time. The script entries respectively have different state transition conditions, in case when the number of said script entries for said state number is two or more.
Therefore, the degree of freedom for the array-type processor to achieve a state transition becomes higher. Therefore, the control operation becomes easier as a result.
In addition, in accordance with the present invention, in the array-type processor, the sequencer section generates an event identifying code from an event and searches said state transition table memory using the state number at a point of time and the event identifying code. When there is found in the search an entry which has a state number matching the state number at a point of time and for which the event identifying code satisfies the state transition condition, a state of the state transition destination is determined according to the state number at a subsequent point of time in the entry.
In the structure of the array-type processor, a destination of state transition can be determined by an operation in which the sequencer generates an event identifying code from an event and make a search through a state transition table memory. This increases the degree of freedom to select a control method.
Additionally, in accordance with the present invention, in the array-type processor, when the event is not notified, said sequencer section generates an event identifying code indicating that the event is not generated and searches said state transition table memory using a combination of the state number at a point of time and the event identifying code.
Consequently, in the array-type processor, even no event is generated, the sequencer can make a search through the state transition table memory to determine a destination of state transition.
Furthermore, in accordance with the present invention, in the array-type processor, the sequencer section generates an event identifying code from an event and searches said event state transition table using the state number at a point of time and the event identifying code and searches said default transition table memory using the state number at a point of time. When there is found in the search an entry for which the state number and the event identifying code result in a matching state, a state of the state transition destination is determined according to the state number at a subsequent point of time in the entry. When there is not found in the search an entry for which the state number and the event identifying code result in a matching state, a state of the state transition destination is determined according to the state number of a subsequent point of time in the script entry in the default state transition table for which the state number at a point of time results in a matching state.
In this manner, the array-type processor can determine a destination of state transition and the degree of freedom for selection of a control method is increased.
Moreover, in accordance with the present invention, in the array-type processor, the state number at a point of time and the event identifying code is inputted to a content address memory including said state transition table. A collation is concurrently conducted for the content address memory and the script entry. When the collation results in a matching state for the script entry, the state number at a next point of time of the script entry is outputted from the content address memory.
In this construction of the array-type processor, the state transition memory is adopted as a content address memory, and a state number at a subsequent point of time can be produced by achieving a collation through the content address memory. The control method can be more freely selected.
Additionally, in accordance with the present invention, in the array-type processor, when after start or completion of generation of the second state number of the subsequent point of time, an address of said instruction memory and/or an address of said connection layout information memory corresponding to the state of the state transition destination.
Therefore, in the array-type processor, the degree of freedom is increased for communication of signals between the state transition control section and the data path section. The array-type processor can achieve a flexible control operation for detailed items.
In accordance with the present invention, when the state of the state transition destination thus determined is assumed as the state at a point of time by the state transition control section, the system starts generating the address corresponding to the state at a point of time.
Therefore, the array-type processor can continuously achieve the same state transition.
In addition, in accordance with the present invention, the array-type processor further includes a register in a path from the start of generation of the address to when the address of said instruction code memory and/or the address of said connection layout information memory reach/reaches said processor elements and said programmable switch elements. The address generation start point of time and the point of time when said processor elements and said programmable switch elements receive the addresses/address are assigned to mutually different cycles.
In the array-type processor, the address generation start point and the point of time when the processor elements and the programmable switch elements receive an address are assigned to mutually different cycles. This leads to increase in the operation speed for the following reasons. The operation xe2x80x9cprocessing operation+event propagation+address distributionxe2x80x9d is not assigned to one cycle. Namely, the operation xe2x80x9cprocessing operation+event propagationxe2x80x9d and the operation xe2x80x9caddress distributionxe2x80x9d are assigned to mutually different cycles. This makes it possible to beforehand issues addresses, and hence the delay in this point of a critical path can be removed.
Further more, in accordance with the present invention, the array-type processor, when said state transition control section determines that the state of the state transition destination matches the state at a point of time, generation of the address corresponding to the state at a point of time is started.
Thanks to the structure, the array-type processor can consecutively execute the same state transition.
Moreover, in accordance with the present invention, the array-type processor, a period of time from when the generation of the address is started to when the address of said instruction code memory and/or the address of said connection layout information memory reach/reaches said processor elements and said programmable switch elements is assigned to one independent cycle.
Consequently, in the structure of the array-type processor, the address generation start point and the point of time when the processor elements and the programmable switch elements receive an address are assigned to mutually different cycles. This increases the operation speed. Using registers and the like, the operation xe2x80x9cprocessing operation +event propagationxe2x80x9d and the operation xe2x80x9caddress distributionxe2x80x9d can be assigned to mutually different cycles. This minimized the critical path and hence the operation speed is increased.
Additionally, in accordance with the present invention, the array-type processor further comprises a first register on a connection line to propagate the event identifying code from said sequencer section to said state transition table memory. The first register temporarily keeps the event identifying code on said connection line to thereby separate a cycle in which the address generation start point exists from a cycle in which said processor elements and said programmable switch elements receive the address of said instruction code memory and/or the address of said connection layout information memory.
In this construction, the array-type processor can operate such that the point of time of the instruction code address generation and the point of time of arrival of the generated instruction code address at the processor elements 105 and the programmable switch elements 106 are respectively in different cycles. Therefore, the instruction code address can be issued at timing independent of other configurations or sections, and hence the control operation can be achieved with higher reliability.
In addition, in accordance with the present invention, in the array-type processor, the state transition table memory includes one or more second registers each of which keeps the state number at the subsequent point of time in each entry including the state number at a point of time. The state transition table memory selects and outputs, when the state transition condition is satisfied, either one of the state numbers of the subsequent points of time kept in said second registers, the selected one state number satisfying the state transition condition.
Thanks to the constitution, in the array-type processor, an instruction code address for a state number at a subsequent point of time can be issued to the data path section regardless of presence or absence of an input of a state number at a point of time to the event state transition table. This consequently improves reliability of the control operation.
Furthermore, in accordance with the present invention, the array-type processor further comprises a selector for selecting whether or not each of said first and second registers is to be used. The instruction code includes control information for controlling whether or not said first register and said second register are to be used. The selector selects, according to said instruction code, whether or not said first register and said second register are to be used.
By the construction, the array-type processor can execute the control operation more precisely according to the state. This advantageously leads to improvement of reliability of the control operation.
Moreover, in accordance with the present invention, the array-type processor, the state transition control section includes a clock signal input terminal and synchronizes operation of a transition of the operation state at a rising point and/or a falling point of a clock signal inputted to said clock signal input terminal.
In the array-type processor, since the operation of state transition between operation states is carried out in at synchronized timing, the control operation can be accomplished with high precision.
Additionally, in accordance with the present invention, in the array-type processor, the state transition control section forcibly conducts a transition of the operation state by a forced state transition signal to cause a state transition regardless of the operation state at the current point.
Therefore, the array-type processor forcibly conducts a transition between operation states, and hence the control operation can be easily achieved.
Additionally, in accordance with the present invention, the array-type processor, the state transition table includes a forced state transition table to detect a matching state with respect to the event identifying code inputted thereto. When said forced state transition table contains a script entry matching the event identifying code inputted to said state transition table, a state number of a subsequent point of time described in the entry is forcibly set as a state of the state transition destination.
As above, in the constitution of the array-type processor, a transition between operation states is forcibly carried out. This advantageously facilitates the control operation.
Furthermore, in accordance with the present invention, the array-type processor, the state transition control section includes an operation control information memory for controlling said data path section.
Consequently, with provision of the operation control information memory, the array-type processor can efficiently control the data path section.